package com.captain.leetcode;

/**
 * @author captain
 * @Des 给你两个二进制字符串，返回它们的和（用二进制表示）。
 * <p>
 * 输入为 非空 字符串且只包含数字 1 和 0。
 * <p>
 * 输入: a = "11", b = "1"
 * 输出: "100"
 * 示例 2:
 * <p>
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 * @Date 2021/8/1 22:08
 */
public class 二进制求和67 {
    public static void main(String[] args) {
        //"100"
        //"110010"
        System.out.println(new 二进制求和67().addBinary("100", "110010"));

    }

    public String addBinary(String a, String b) {
        int m = a.length() - 1;
        int n = b.length() - 1;

        StringBuilder builder = new StringBuilder();

        char carry = '0';
        char last = '0';
        int index = 0;
        for (int i = m, j = n; i >= 0 && j >= 0; i--, j--) {
            //记录两者不一样的时候
            index++;
            char am = a.charAt(i);
            char cn = b.charAt(j);
            //三种情况
            //1.  1 1 0
            if ((am + cn + carry == 146)) {
                carry = '1';
                builder.append('0');
                //1 0 0
            } else if ((am + cn + carry == 145)) {
                carry = '0';
                builder.append('1');
                //1 1 1
            } else if ((am + cn + carry == 144)) {
                carry = '0';
                builder.append('0');
            } else if ((am + cn + carry == 147)) {
                carry = '1';
                builder.append('1');
            }
            //110
            if (a.charAt(0) + b.charAt(0) + carry > 145) {
                last = '1';
            }
        }
        if (index - 1 == m && index - 1 == n) {
            if (last == '0') return builder.reverse().toString();
            return builder.append('1').reverse().toString();
        }
        //继续遍历a
        //110
        if (m > n) {
            nextLoop(index, a, builder, carry);
            return builder.reverse().toString();
        } else {
            nextLoop(index, b, builder, carry);
            return builder.reverse().toString();
        }
    }

    public void nextLoop(int index, String a, StringBuilder builder, char carry) {
        int m = a.length() - 1;
        for (int i = m - index; i >= 0; i--) {
            char ac = a.charAt(i);
            //11
            if (ac + carry == 98) {
                builder.append('0');
                carry = '1';
            } else if (ac + carry == 96) {
                builder.append('0');
                carry = '0';
            } else {
                builder.append('1');
                carry = '0';
            }
        }
        if (carry == '1') {
            builder.append('1');
        }
    }
}
